Many microprocessors such as the popular Intel X86 series and their clones contain apparatus for computing exponential and trigonometric functions. Such functions are useful in diverse areas of engineering, science, and mathematics, as well as in computer graphics applications. Using previously known methods, such functions may take a long time to compute. For example, the computation of sine and cosine functions can take approximately 100 clock cycles for some operands on the Intel Pentium processor and more than 300 clock cycles on the Intel 486..sup.1 FNT .sup.1 This information came from a document entitled "Everything You Always Wanted to Know about Math Coprocessors," published on the Internet by Norbert Juffa.
We will now reference various known types of circuits for computing exponential and trigonometric functions.
1. Table lookup method. The pure table lookup method involves keeping a table of the values of the function to be computed for every possible argument x. This approach was seriously considered for 16 bits of precision, but is no longer feasible for higher precision processors such as the high-end processors of today. Table-lookups are now only feasible for approximating such functions, as disclosed in U.S. Pat. No. 5,224,064, entitled "Transcendental Function Approximation Apparatus and Method," to M. Henry and G. Martin.
2. Polynomial approximation method. For example one could compute e.sup.x by using the first "few" terms of the infinite series ##EQU1## This series converge quickly for small values of x but converges too slowly for larger values of x. There are other series than power series that may lead to better convergence. However, it is not clear how to speed up such a procedure further. For example, it is not clear how to combine several iterations into one.
3. Combined method. It is possible to combine the two aforementioned methods. Tang, for example, (P. T. P. Tang, "Table-lookup algorithms for elementary functions and their error analysis," Proc. 10th Symp. Computer Arith.) designed such a method, which is used in the Intel Pentium processor. However, like the previous method, it is not clear how to speed up such a procedure further. PA1 4. Method of rational approximation. This method is efficient, but requires a very fast divider, which is expensive. PA1 5. Digit-by-digit methods. This class of methods, which includes the new one discussed in this document, is a very commonly used class of methods for hardware evaluation of exponential, trigonometric, and other transcendental functions. The methods in this class are based on simple iterative equations that imply only addition/subtraction and shift operations. Simple as the methods may be, they traditionally suffer from slow linear convergence. PA1 These iterative methods were first discovered by Volder (J. E. Volder, "The CORDIC Trigonometric Computing Technique," IRE Trans. Electronic Computers," Vol. 8, pp. 330-334, 1959). Recent references include a U.S. Patent (Nakayama, U.S. Pat. No. 4,956,799, Sep. 11, 1990) where the inventor called these iterative methods "pseudo-division." PA1 The principles behind these iterative methods for computing transcendental functions will now be described. PA1 The basic, well-known method for computing e.sup.x for x.di-elect cons.[0, ln 2) involves 2 recurrences, as follows: EQU x.sub.i+1 =x.sub.i -ln b.sub.i (1) EQU y.sub.i+1 =y.sub.i b.sub.i (2) PA1 Here x.sub.0 is the operand, x, where x can be limited to the range [0, ln 2) because any computation of e.sup.x where x is not in this range can be reduced to a computation of e.sup.x where x is in this range. (Israel Koren's book entitled Computer Arithmetic Algorithms, Prentice-Hall, 1993, explains this point as well as the entire traditional algorithm.) PA1 We iterate according to (1) until x.sub.n =0 for some n. We then have x.sub.n =0=x.sub.0 -.SIGMA..sub.i=1.sup.n-1 ln b.sub.i, that is, x.sub.0 =ln .PI..sub.i=0.sup.n-1 b.sub.i. Hence it follows that .PI..sub.i=0.sup.n-1 b.sub.i =e.sup.x0, which is e.sup.x. Solving the recurrence (2) for y.sub.n yields y.sub.n =y.sub.0 .PI..sub.i=0.sup.n-1 b.sub.i =y.sub.0 e.sup.x, which is just slightly more general than e.sup.x. Thus the task of computing e.sup.x is reduced to the task of finding a sequence {b.sub.i } and a number n such that .SIGMA..sub.i=0.sup.n-1 ln b.sub.i =x and then computing y.sub.0 .PI..sub.i=0.sup.n-1 b.sub.i. In order to be useful, the b.sub.i 's must not merely exist, but it must also be easy to compute a product by each b.sub.i. It turns out that if b.sub.i =1+s.sub.i 2.sup.-i, where s.sub.i =0 or 1 would satisfy the aforementioned properties. PA1 The remaining thing to consider is how to choose s.sub.i for each i to guarantee convergence of the x.sub.i 's to zero. It turns out that we can pick s.sub.i by trial subtraction: First try picking s.sub.i to be 1, yielding x.sub.i+1 =x.sub.i -ln(1+2.sup.-i). If x.sub.i+1 &gt;0, then the choice of s.sub.i is correct. PA1 But otherwise, choose s.sub.i =0 instead, yielding x.sub.i+1 =x.sub.i. This process is akin to that of bit-by-bit division, hence the name "pseudodivision" for these iterations. PA1 It is not apparent how to combine several such iterations into 1 step.
Ercegovac (M. Ercegovac, "Radix-16 Evaluation of Certain Elementary Functions," IEEE Trans. Comput., C-22: 561-566 (1973)) showed how to compute the logarithm and exponential functions in radix-16. However, each iteration is done at a fairly high cost, and it is not clear how Ercegovac's scheme can be adapted to the computation of sine and cosine.
Accordingly, notwithstanding the abovementioned methods used in machinery for computing exponential and trigonometric functions, there continues to be a need for new types of machinery for computing such functions that are fast and not too large.